A program is a list of statements. This list of statements may be translated, through processes that include compilation, to produce an executable file that can cause a computer to perform a desired action. One type of statement is an assignment statement. An illustrative example of an assignment statement is x=y. This statement may be translated to mean that y is assigned to x, or more specifically, the value of the variable y is assigned to the variable x.
One type of variable is a pointer. Pointers are often used in programs because they offer flexibility in creating compact and efficient executable files. A pointer contains a location (or address) of another variable. Thus, a pointer points to another variable. Through a pointer, the value of another variable may be changed. In this way, a pointer indirectly references another variable.
It is beneficial to analyze programs in order to obtain information that may be used to improve them. In order to analyze a program that uses pointers, an analysis is performed that focuses on statements that involve pointers. Such pointer analysis yields sets of information about pointers in the program. The precision of a pointer analysis is determined by the size of these sets of information. The larger the set the less precise is the information.
Current pointer analyses suffer from the extremes of an inverse relationship between time and information. One type of analysis can be performed quickly by using a technique of unification but provides imprecise results due to the production of large sets of information. Another analysis by Lars Ole Andersen provides results that are much more precise by producing small sets of information but requires a prohibitively long amount of time. See Lars Ole Andersen, Program Analysis and Specialization for the C Programing Language (1994) (published Ph.D. dissertation, University of Copenhagen). Thus, current pointer analyses are either too costly in terms of time or too imprecise in terms of information. Tools that rely on such pointer analyses such as optimizer and debugging tools have been constrained by having to make inferior assumptions about behaviors of programs. As the size of programs has increased with each generation of technology, such inferior assumptions may slow the improvement of programs and lead to the eventual lack of acceptance of such programs in the marketplace.
Thus, what is needed are systems, methods, and structures to enhance pointer analysis of programs so as to allow a desired level of analytical precision within a desired duration of analysis.